package code;

import java.util.Arrays;

public class VerifySquenceOfBST {
    public boolean Solution(int [] sequence) {
        if(sequence.length==0){
            return false;
        }
        boolean flag;
        flag = verifySub(sequence);
        return flag;
    }

    boolean verifySub(int [] sequence){
        int i=0;
        boolean flag=true;
        if(sequence.length==0){
            return flag;
        }
        for(i=0;i<sequence.length-1;i++){
            if(sequence[i]>sequence[sequence.length-1]){
                break;
            }
        }
        for (int j=i;j<sequence.length-1;j++){
            if(sequence[j]<sequence[sequence.length-1]){
                return false;
            }
        }
        int[] left = new int[i];
        System.arraycopy(sequence,0,left,0,i);
        flag = verifySub(left);

        int[] right = new int[sequence.length-i-1];
        System.arraycopy(sequence,i,right,0,sequence.length-i-1);
        flag = verifySub(right);

        return flag;
    }

    public static void main(String[] avgr){
        VerifySquenceOfBST verifySquenceOfBST = new VerifySquenceOfBST();
        int[] test = new int[]{2,9,5,16,17,15,19,18,12};
        System.out.println(verifySquenceOfBST.Solution(test));
    }
}
